This invention relates to systems and methods for generating and decoding graphical bar codes.
A typical bar code symbol is a pattern of parallel bars and spaces of various widths that represent data elements or characters. The bars represent strings of binary ones and the spaces represent strings of binary zeros. A conventional xe2x80x9cone-dimensionalxe2x80x9d bar code symbol contains a series of bars and spaces that vary only in a single dimension. One-dimensional bar code symbols have relatively small information storage capacities. xe2x80x9cTwo-dimensionalxe2x80x9d bar codes have been developed to meet the increasing need for machine-readable symbols that contain more information than one-dimensional bar code symbols. The information storage capacity of two-dimensional bar code symbols is increased relative to one-dimensional bar codes by varying the bar code patterns in two dimensions. Common two-dimensional bar code standards include PDF417, Code 1, and Maxicode. One-dimensional and two-dimensional bar code symbols typically are read by optical scanning techniques (e.g., by mechanically scanned laser beams or by self-scanning charge-coupled devices (CCD""s)) that convert a printed bar code symbol into electrical signals. The electrical signals are digitized and decoded to recover the data encoded in the printed bar code symbol.
Bar codes may be used in a variety of applications, including low information content applications (e.g., automatic price tagging and inventory management), and relatively high information content applications (e.g., encoding mail addresses and postage for automated mail reading and mail distribution systems, and encoding compressed content of a printed page).
As used herein, the term xe2x80x9cgraphical bar codexe2x80x9d broadly refers to an image that contains inconspicuous graphical modulations that encode embedded information.
The invention features an inventive scheme (systems and methods) for generating and decoding graphical bar codes characterized by relatively high information capacity and pleasing visual appearances that correspond substantially to their respective base image patterns.
In one aspect of the invention, an invertible graphical operation is applied between regions of a base image and information-encoding graphical templates that are selected from a predefined template set to produce a graphical bar code with regions from which graphical templates are recoverable by applying an inverse graphical operation between graphical bar code regions and corresponding base image regions.
Embodiments in accordance with this aspect of the invention may include one or more of the following features.
In some embodiments, the invertible graphical operation corresponds to an exclusive OR (XOR) operation. In these embodiments, XOR operations may be applied between the graphical bar code regions and corresponding base image regions to produce the graphical templates.
In some embodiments, each of the base image regions and the graphical templates has the same number of pixels. Each of the base image regions and the graphical templates preferably has the same pixel layout (e.g., a rectangular or non-rectangular pixel array).
Each graphical template preferably comprises a pattern of bright and dark pixels. The number of bright pixels preferably is greater than the number of dark pixels. Each pixel location within the predefined template set preferably has an equal probability of being a dark pixel.
In some embodiments, the graphical templates may be ordered adaptively in accordance with one or more predefined rules relating to disfavored graphical template sequences.
In another aspect of the invention, an invertible graphical operation is applied is between regions of a graphical bar code and corresponding regions of a base image to produce a set of measurement blocks, and information-encoding graphical templates corresponding to the set of measurement blocks with the highest estimated probability is selected from a predefined template set.
Embodiments in accordance with this aspect of the invention may include one or more of the following features.
The invertible graphical operation preferably corresponds to an XOR operation.
In some embodiments, pixel value probabilities preferably are computed for each of the measurement blocks. The pixel value probabilities may be computed for a given measurement block based upon a weighted average of gray value measurements over the given measurement block. The weighted average of gray values may be computed by fitting a mask (e.g., a mask having a truncated Gaussian profile) to the dot locations over the given measurement block. Parameters of probability distributions (e.g., asymmetric Laplacian distributions) that are fit to a histogram of the weighted average of gray value measurements may be estimated.
Other features and advantages of the invention will become apparent from the following description, including the drawings and the claims.